package com.my.sort.v2;

import com.my.sort.Sortable;

/**
 * Created by ZhongGang
 * at 2018/10/9 16:24
 * <p>
 * 快速排序
 */
public class QuickSorter<T extends Comparable<T>> implements Sortable<T> {

    @Override
    public T[] sort(T[] elements) {
        if (elements == null || elements.length < 2) {
            return elements;
        }

        quick(elements, 0, elements.length - 1);

        return elements;
    }

    private void quick(T[] elements, int left, int right) {
        if (left >= right) {
            return;
        }

        T pivotElement = elements[left];
        int low = left;
        int high = right;
        int tmpIndex;
        while (low < high) {

            while (low < high && elements[high].compareTo(pivotElement) >= 0) {
                high -= 1;
            }

            elements[low] = elements[high];

            while (low < high && elements[low].compareTo(pivotElement) <= 0) {
                low += 1;
            }

            elements[high] = elements[low];
            tmpIndex = low;

            elements[tmpIndex] = pivotElement;
        }

        quick(elements, left, low - 1);
        quick(elements, low + 1, right);
    }
}
